package com.hqq.graph;

/**
 * UndirectedGraph
 * 无向图的API
 * Created by heqianqian on 2017/8/6.
 */
public class UndirectedGraph implements Graph {

    @Override
    public int vertexCount() {
        return 0;
    }

    @Override
    public int edgeCount() {
        return 0;
    }

    @Override
    public void addEdge(int v, int w) {

    }

    @Override
    public Iterable<Integer> adjVertex(int v) {
        return null;
    }

    /**
     * 计算V的度数
     * 度数:和该顶点关联的边的条数
     */
    public int degree(UndirectedGraph graph, int v) {
        int degree = 0;
        for (int w : graph.adjVertex(v)) {
            degree++;//相邻顶点个数
        }
        return degree;
    }

    /**
     * 计算所有顶点的最大度数
     */
    public int maxDegree(UndirectedGraph graph) {
        int maxDegree = 0;
        for (int v = 0; v < graph.vertexCount(); v++) {
            if (degree(graph, v) > maxDegree) {
                maxDegree = degree(graph, v);
            }
        }
        return maxDegree;
    }

    /**
     * 计算所有顶点的平均度数
     */
    public int avgDegree(UndirectedGraph graph) {
        return 2 * graph.edgeCount() / graph.vertexCount();
    }

    /**
     * 计算图中的自环个数
     * 自环:一条连接一个顶点和其自身的边
     */
    public int numberOfSelfLoops(UndirectedGraph graph) {
        int selfCount = 0;
        for (int v = 0; v < graph.vertexCount(); v++) {
            for (int w : graph.adjVertex(v)) {
                if (w == v) {
                    selfCount++;
                }
            }
        }
        return selfCount / 2;
    }

    @Override
    public String toString() {
        String s = vertexCount() + " vertices, " + edgeCount() +
                " edges\n";
        for (int v = 0; v < vertexCount(); v++) {
            s += v + ": ";
            for (int w : this.adjVertex(v)) {
                s += w + " ";
            }
            s += "\n";
        }
        return s;
    }
}
